We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77)of a given string of length $N$ in linear time, that utilizes only $N\log N +O(1)$ bits of working space, i.e., a single integer array, for constant sizeinteger alphabets. This greatly improves the previous best space requirementfor linear time LZ77 factorization (K\"arkk\"ainen et al. CPM 2013), whichrequires two integer arrays of length $N$. Computational experiments show thatdespite the added complexity of the algorithm, the speed of the algorithm isonly around twice as slow as previous fastest linear time algorithms.
展开▼
机译：我们提出了一种新算法，用于计算线性时间中给定长度$ N $的字符串的Lempel-Ziv因式分解（LZ77），该算法仅利用$ N \ log N + O（1）$位工作空间，即单个整数数组，用于恒定的sizeinteger字母。这极大地改善了线性时间LZ77分解的先前最佳空间要求（K \“ arkk \” ainen等人，CPM 2013），这需要两个长度为$ N $的整数数组。计算实验表明，尽管增加了算法的复杂性，但算法的速度仅是以前最快的线性时间算法的两倍左右。
展开▼
